The invention relates to computer image and computer graphics processing systems and, more particularly, to methods and apparatus for manipulating images within an image or graphics processing system.
Generally, digitized images contain rows of pixels that, when taken together, form an image upon a computer screen or can be printed by a computer printer. Each pixel is typically defined by a value and a location. The pixel value, commonly a 24-bit word, defines a pixel intensity and a pixel color. The pixel location is defined by a coordinate within a Cartesian coordinate system. To display an image comprised of an array of such pixels, a computer system generates a display by displaying each pixel in a raster scan pattern.
Such digitized images can be created from "hardcopy" images by conventional scanner hardware. Alternatively, digitized images can be directly created by a computer graphics (drawing) program, a "frame grabber" and the like. Once the image is created and stored within a computer system, a user can manipulate the image by, for example, rotating, scaling, magnifying, and perspective warping. Such manipulations are generally known in the art as image transformations.
To facilitate most image transformations, the coordinate system of an original image is transformed into a coordinate system for a transformed image. Consequently, a transformation can be represented as a matrix function. Equation 1 depicts the general form of a matrix function for implementing conventional transformations. ##EQU1## where: (u,v) defines a location of a pixel in the coordinate system for the original image (digitized input image);
(x,y) defines a location of a pixel in the coordinate system for the transformed image (output image); and a, b, c, d define the transformation function.
For example, Table 1 shows illustrative matrix variables to perform certain transformations.
TABLE 1 ______________________________________ Illustrative Transformation Values TRANSFORMATION a b c d ______________________________________ Scaling S.sub.h 0 S.sub.v 0 Skewing 1 0 1 H.sub.h Counterclockwise cos .theta. sin .theta. -sin .theta. cos .theta. Rotation ______________________________________
S.sub.h and S.sub.v respectively are horizontal and vertical scale factors, H.sub.h is a shear factor, and .theta. is a rotation angle. Using these matrix variables, or a combination thereof, a given pixel within an image can be scaled, skewed, or rotated from its original location in the input image. By repeatedly applying such matrices to each pixel in an input image, an entire image can be transformed.
To simplify the computation in performing a transformation, the two-dimensional transformations can often be represented as a cascade of one-dimensional transformations. For example, to perform a scaling transformation, each dimension of the image can be scaled independently. Equation 2 depicts such a transformation. ##EQU2##
Furthermore, there have been numerous methods proposed by those skilled in the art for performing multi-step rotation transformation, e.g., 2-, 3-, and 4-step rotation transformations. In each multi-step rotation transformation, the goal is to perform the transformation mathematics in an efficient process, i.e., simplifying the matrix calculation. Typically, this means performing triangular decomposition upon the transformation matrix. As such, the general form of, for example, a rotation matrix is decomposed into a cascade of upper and lower triangular matrices. For example, Equation 3 is a 2-step rotation transformation containing an upper and a lower triangular matrix. ##EQU3## The first matrix (left) in Equation 3 performs a horizontal shear combined with a horizontal scale, while the second matrix (right) performs a vertical shear and a vertical scale. After applying both matrixes to coordinates (u,v), the output coordinates (x,y) are rotated relative to the (u,v) coordinates.
Equation 4 is an illustrative 3-step rotation transformation containing two upper triangular matrices and a lower triangular matrix. ##EQU4## In Equation 4, the first and third matrices perform horizontal shear functions, while the second matrix performs a vertical shear function. The result of applying this cascade of matrices to a pixel location is a rotation of that location.
Equation 5 is an illustrative 4-step rotation transformation containing an upper triangular matrix and three lower triangular matrices. ##EQU5## In Equation 5 (applying the matrices from left to right to coordinates (u,v)), the first matrix performs a vertical shear function, the second matrix performs a horizontal shear function, the third matrix performs a vertical scale function, and the fourth matrix performs a horizontal scale function. In combination, this cascade of matrices rotates the pixel location.
Such transformation matrices as those shown above have been disclosed in: E. Catmull et al., "3-D Transformations of Images in Scanline Order", Association for Computing Machinery (ACM): Proceedings of Siggraph '80, pp. 279-285 (1980); C.F.R. Weiman, "Continuous Anti-Aliasing Rotation and Zoom of Raster Images", Association for Computing Machinery (ACM): Proceedings of Siggraph '80, pp. 286-293 (1980); C. Braccini et al., "Fast Geometrical Manipulations of Digital Images", Computer Graphics and Image Processing, No. 13, pp. 127-141 (1980); and Tanaka et al., U.S. Pat. No. 4,759,076, issued Jul. 19, 1988.
If a scaling function as well as a rotation function is desired, an image processing system would typically have to solve six matrix multiplications, e.g., four from Equation 5 and two from Equation 2. Thus, a combination scaling and rotating function requires an excessive amount of computations to perform. This is especially time consuming when a high resolution image is being transformed, i.e., each pixel in the millions of pixels comprising the image must be transformed.
Therefore, a need exists in the art for a method and apparatus for efficiently scaling and rotating images using less computational steps than presently are used in the prior art.